import java.util.*;

public class CharTree {
    private Character data;
    private CharTree left;
    private CharTree right;



    public static void main(String[] args) {
        char[]  pre =new char[] {'A','B','C','D','E','F'};
        char[]  mid =new char[] {'C','B','D','A','E','F'};
        CharTree tree=buildTree(pre,mid);
//        printPre(tree);
//        System.out.println();
//        printMid(tree);

        Map<Integer, List<Character>> map =new HashMap<Integer, List<Character>>();
        List<Character> list =new ArrayList<>();
        list.add(tree.getData());
        map.put(0,list);
        printreeWide(tree.getLeft(),tree.getRight(),map,1);

        for(Integer i:map.keySet()){
            List<Character> list1=map.get(i);
            for (Character character : list1) {
                System.out.print(character+",");
            }
            System.out.println();
        }

    }

    private static void printreeWide(CharTree left, CharTree right, Map<Integer, List<Character>> map,Integer n) {
        if(left!=null){
            if(map.containsKey(n)){
                List<Character> list=map.get(n);
                list.add(left.getData());
            }else{
                List<Character> list =new ArrayList<>();
                map.put(n,list);
                list.add(left.getData());
            }
            printreeWide(left.getLeft(),left.getRight(),map,n+1);
        }
        if(right!=null){
            if(map.containsKey(n)){
                List<Character> list=map.get(n);
                list.add(right.getData());
            }else{
                List<Character> list =new ArrayList<>();
                map.put(n,list);
                list.add(right.getData());
            }
            printreeWide(right.getLeft(),right.getRight(),map,n+1);
        }






    }

    private static void printMid(CharTree tree) {
        if(tree.getLeft()!=null){
            printMid(tree.getLeft());
        }
        System.out.print(tree.getData()+",");
        if(tree.getRight()!=null){
            printMid(tree.getRight());
        }
    }

    private static void printPre(CharTree tree) {
        System.out.print(tree.getData()+",");
        if(tree.getLeft()!=null){
            printPre(tree.getLeft());
        }
        if(tree.getRight()!=null){
            printPre(tree.getRight());
        }
    }

    private static CharTree buildTree(char[] pre, char[] mid) {
        Character root =pre[0];
        CharTree tree =new CharTree(root);
        int index = 0;
        for(int i=0;i<mid.length;i++){
            if(mid[i]==root){
                index=i;
            }
        }
        if(index>0){
        tree.setLeft(buildTree(Arrays.copyOfRange(pre,1,index+1), Arrays.copyOfRange(mid,0,index)));
        }
        if(index<mid.length-1){
        tree.setRight(buildTree(Arrays.copyOfRange(pre,index+1,pre.length), Arrays.copyOfRange(mid,index+1,mid.length)));
        }

        return tree;
    }

    public CharTree(Character data) {
        this.data = data;
    }

    public Character getData() {
        return data;
    }

    public void setData(Character data) {
        this.data = data;
    }

    public CharTree getLeft() {
        return left;
    }

    public void setLeft(CharTree left) {
        this.left = left;
    }

    public CharTree getRight() {
        return right;
    }

    public void setRight(CharTree right) {
        this.right = right;
    }
}
